{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Take K of Each Character From Left and Right"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: takeCharacters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每种字符至少取 K 个"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由字符 <code>'a'</code>、<code>'b'</code>、<code>'c'</code> 组成的字符串 <code>s</code> 和一个非负整数 <code>k</code> 。每分钟，你可以选择取走 <code>s</code> <strong>最左侧</strong> 还是 <strong>最右侧</strong> 的那个字符。</p>\n",
    "\n",
    "<p>你必须取走每种字符 <strong>至少</strong> <code>k</code> 个，返回需要的 <strong>最少</strong> 分钟数；如果无法取到，则返回<em> </em><code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aabaaaacaabc\", k = 2\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>\n",
    "从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。\n",
    "从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。\n",
    "共需要 3 + 5 = 8 分钟。\n",
    "可以证明需要的最少分钟数是 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a\", k = 1\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>无法取到一个字符 'b' 或者 'c'，所以返回 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 仅由字母 <code>'a'</code>、<code>'b'</code>、<code>'c'</code> 组成</li>\n",
    "\t<li><code>0 &lt;= k &lt;= s.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [take-k-of-each-character-from-left-and-right](https://leetcode.cn/problems/take-k-of-each-character-from-left-and-right/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [take-k-of-each-character-from-left-and-right](https://leetcode.cn/problems/take-k-of-each-character-from-left-and-right/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabaaaacaabc\"\\n2', '\"a\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        sz = len(s)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        freq = Counter()\n",
    "        s += s\n",
    "        result = -1\n",
    "        while i <= sz and j < 2 * sz:\n",
    "            ch_j = s[j]\n",
    "            j += 1\n",
    "            freq[ch_j] += 1\n",
    "            if j < sz:\n",
    "                continue\n",
    "            while j - i > sz:\n",
    "                ch_i = s[i]\n",
    "                freq[ch_i] -= 1\n",
    "                i += 1\n",
    "            while i <= sz and i < j:\n",
    "                distance = j - i\n",
    "                flag = True\n",
    "                for ch in \"abc\":\n",
    "                    if ch not in freq or freq[ch] < k:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    # print(i, j, s[i:j])\n",
    "                    if result < 0 or distance < result:\n",
    "                        result = distance\n",
    "                    ch_i = s[i]\n",
    "                    freq[ch_i] -= 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        c = {'a':0, 'b':0, 'c':0}\n",
    "        for ch in s:\n",
    "           c[ch] += 1\n",
    "        for e in c:\n",
    "            if c[e] < k:\n",
    "                return -1\n",
    "        \n",
    "        # print(c)\n",
    "        d = {'a':0, 'b':0, 'c':0}\n",
    "        right = 0\n",
    "        res = 0\n",
    "        for left in range(len(s)):\n",
    "            # print(d)\n",
    "            if right < left:\n",
    "                right = left\n",
    "\n",
    "            while right < len(s) and d[s[right]] < c[s[right]] - k:\n",
    "                d[s[right]] += 1\n",
    "                right += 1\n",
    "\n",
    "            res = max(res, right - left)\n",
    "            if left < right:\n",
    "                d[s[left]] -= 1\n",
    "\n",
    "        return len(s) - res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\r\n",
    "        n = len(s)\r\n",
    "        cnt = Counter(s)\r\n",
    "        if cnt['a'] < k or cnt['b'] < k or cnt['c'] < k:\r\n",
    "            return -1 \r\n",
    "        l = 0 \r\n",
    "        # 正难则反，取走最少等于剩余最多 且剩余是连续的 \r\n",
    "        # \r\n",
    "        res = n\r\n",
    "        for i, x in enumerate(s):\r\n",
    "            cnt[x] -= 1\r\n",
    "            while cnt[x] < k:\r\n",
    "                cnt[s[l]] += 1 \r\n",
    "                l += 1 \r\n",
    "            res = min(res, n -(i - l + 1))\r\n",
    "        return res \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        j = n = len(s)\n",
    "        c = Counter()\n",
    "        while c['a'] < k or c['b'] < k or c['c'] < k:\n",
    "            if j == 0: return -1  # 所有字母都取也无法满足要求\n",
    "            j -= 1\n",
    "            c[s[j]] += 1\n",
    "        ans = n - j  # 左侧没有取字符\n",
    "        for i, ch in enumerate(s):\n",
    "            c[ch] += 1\n",
    "            while j < n and c[s[j]] > k:  # 维护 j 的最大下标\n",
    "                c[s[j]] -= 1\n",
    "                j += 1\n",
    "            ans = min(ans, i + 1 + n - j)\n",
    "            if j == n: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        cnt = Counter(s)\n",
    "        def check(cnt):\n",
    "            return cnt['a']<k or cnt['b']<k or cnt['c']<k\n",
    "        if check(cnt):return -1\n",
    "        res = 0\n",
    "        left = 0\n",
    "        for right,c in enumerate(s):\n",
    "            cnt[c]-=1\n",
    "            while check(cnt):\n",
    "                cnt[s[left]]+=1\n",
    "                left+=1\n",
    "            res = max(res,right-left+1)\n",
    "        return len(s)-res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        m = len(s)\n",
    "        cnt = Counter(s)\n",
    "\n",
    "        s = s + s\n",
    "        res = inf\n",
    "        l, r = 0, m\n",
    "\n",
    "        def check():\n",
    "            for c in 'abc':\n",
    "                if cnt[c] < k:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        if not check():\n",
    "            return -1\n",
    "        while l <= m:\n",
    "            while not check():\n",
    "                cnt[s[r]] += 1\n",
    "                r += 1\n",
    "            res = min(res, r - l)\n",
    "            cnt[s[l]] -= 1\n",
    "            l += 1\n",
    "\n",
    "        return -1 if res == inf else res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        #假设前缀为空\n",
    "        j=n=len(s)\n",
    "        c=Counter()\n",
    "        \n",
    "        while c['a']<k or c['b']<k or c['c']<k:\n",
    "            if j==0:\n",
    "                return -1\n",
    "            j-=1\n",
    "            c[s[j]]+=1\n",
    "        ans=n-j\n",
    "\n",
    "        #前缀不为空\n",
    "        for l,ele in enumerate(s):\n",
    "            c[ele]+=1\n",
    "            while j<n and c[s[j]]>k:\n",
    "                c[s[j]]-=1\n",
    "                j+=1\n",
    "            ans=min(ans,l+1+n-j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        j = n = len(s)\n",
    "        c = Counter()\n",
    "        while c['a'] < k or c['b'] < k or c['c'] < k:\n",
    "            if j == 0: return -1  # 所有字母都取也无法满足要求\n",
    "            j -= 1\n",
    "            c[s[j]] += 1\n",
    "        ans = n - j  # 左侧没有取字符\n",
    "        for i, ch in enumerate(s):\n",
    "            c[ch] += 1\n",
    "            while j < n and c[s[j]] > k:  # 维护 j 的最大下标\n",
    "                c[s[j]] -= 1\n",
    "                j += 1\n",
    "            ans = min(ans, i + 1 + n - j)\n",
    "            if j == n: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        j = n = len(s)\n",
    "        c = Counter()\n",
    "        # 前缀为空时，后缀长度\n",
    "        while c['a'] < k or c['b'] < k or c['c'] < k:\n",
    "            if j == 0: return -1  # 所有字母都取也无法满足要求\n",
    "            j -= 1\n",
    "            c[s[j]] += 1\n",
    "        ans = n - j\n",
    "        # 遍历前缀\n",
    "        for i, ch in enumerate(s):\n",
    "            c[ch] += 1\n",
    "            # 去掉多余的后缀\n",
    "            while j < n and c[s[j]] > k:  # 维护 j 的最大下标\n",
    "                c[s[j]] -= 1\n",
    "                j += 1\n",
    "            ans = min(ans, i + 1 + n - j)   # 前缀长度(i+1)+后缀长度(n-j)\n",
    "            if j == n: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        res=Counter()\n",
    "        n=j=len(s)\n",
    "        while res['a']<k or res['b']<k or res['c']<k:\n",
    "            if j==0:\n",
    "                return -1\n",
    "            j-=1\n",
    "            res[s[j]]+=1\n",
    "        ans=n-j\n",
    "\n",
    "        for i,ss in enumerate(s):\n",
    "            res[ss]+=1\n",
    "            while j<n and res[s[j]]>k:\n",
    "                res[s[j]]-=1\n",
    "                j+=1\n",
    "            ans=min(ans,i+1+n-j)\n",
    "            if j==n:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        cnt_a = 0\n",
    "        cnt_b = 0\n",
    "        cnt_c = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == \"a\":\n",
    "                cnt_a += 1\n",
    "            if s[i] == \"b\":\n",
    "                cnt_b += 1\n",
    "            if s[i] == \"c\":\n",
    "                cnt_c += 1\n",
    "        if cnt_a < k or cnt_b < k or cnt_c < k:\n",
    "            return -1\n",
    "        cnt = collections.defaultdict(int)\n",
    "        cnt[\"a\"] = cnt_a - k\n",
    "        cnt[\"b\"] = cnt_b - k\n",
    "        cnt[\"c\"] = cnt_c - k\n",
    "        # print(cnt)\n",
    "        j = 0\n",
    "        d = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # while j <= i:\n",
    "            #     d[s[j]] += 1\n",
    "            #     j += 1\n",
    "            j = max(j, i)\n",
    "            while j < n:\n",
    "                if d[s[j]] == cnt[s[j]]:\n",
    "                    break\n",
    "                d[s[j]] += 1\n",
    "                j += 1\n",
    "            # print(i, j)\n",
    "            ans = max(ans, j - i)\n",
    "            if i < j:\n",
    "                d[s[i]] -= 1\n",
    "            \n",
    "        return n - ans\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        cnt=Counter()\n",
    "        j=n-1\n",
    "        while cnt['a']<k or cnt['b']<k or cnt['c']<k:\n",
    "            if j==-1: return -1\n",
    "            cnt[s[j]] += 1\n",
    "            j-=1\n",
    "        j += 1\n",
    "        ans=n-j\n",
    "        for i,h in enumerate(s):\n",
    "            cnt[h] += 1\n",
    "            while j<n and cnt[s[j]]>k:\n",
    "                cnt[s[j]] -= 1\n",
    "                j += 1\n",
    "            ans=min(ans,i+1+n-j)\n",
    "            if j==n: break\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        j = n = len(s)\n",
    "        c = Counter()\n",
    "        while c['a'] < k or c['b'] < k or c['c'] < k:\n",
    "            j -= 1\n",
    "            if j == -1:\n",
    "                return -1\n",
    "            else:\n",
    "                c[s[j]] += 1\n",
    "        print(c)\n",
    "        ans = n - j\n",
    "        for i in range(n):\n",
    "            c[s[i]] += 1\n",
    "            while j < n and c[s[j]] > k:\n",
    "                c[s[j]] -= 1\n",
    "                j += 1\n",
    "            ans = min(ans, i + 1 + n - j)\n",
    "            if j == n: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        #一样的滑动窗口，一样的具有单调性\n",
    "        left=right=0\n",
    "        dct={}\n",
    "        ans=inf\n",
    "        #先统计窗口内至多的情况\n",
    "        a_num=b_num=c_num=0\n",
    "        for i in s:\n",
    "            if i==\"a\":\n",
    "                a_num+=1\n",
    "            elif i==\"b\":\n",
    "                b_num+=1\n",
    "            else:\n",
    "                c_num+=1\n",
    "        a_num-=k;b_num-=k;c_num-=k\n",
    "        if a_num<0 or b_num<0 or c_num<0:\n",
    "            return -1\n",
    "        #现在就是至多了，然后考虑尽可能多的情况\n",
    "        while right<len(s):\n",
    "            if s[right] not in dct:\n",
    "                dct[s[right]]=1\n",
    "            else:\n",
    "                dct[s[right]]+=1\n",
    "            while dct.get(\"a\",-1)>a_num or dct.get(\"b\",-1)>b_num or dct.get(\"c\",-1)>c_num:\n",
    "                dct[s[left]]-=1\n",
    "                left+=1\n",
    "            ans=min(ans,len(s)-(right-left+1))\n",
    "            right+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        j = n\n",
    "        cnt = defaultdict(int)\n",
    "        # 不取走左侧字符的情况\n",
    "        while cnt['a'] < k or cnt['b'] < k or cnt ['c'] < k:\n",
    "            if j == 0: return -1\n",
    "            j -= 1\n",
    "            cnt[s[j]] += 1\n",
    "        res = n - j\n",
    "\n",
    "        # 取走左侧字符的情况\n",
    "        for i, c in enumerate(s):\n",
    "            cnt[c] += 1\n",
    "            while j < n and cnt[s[j]] > k:\n",
    "                cnt[s[j]] -= 1\n",
    "                j += 1\n",
    "            res = min(res, i + n - j + 1)\n",
    "            if j == n: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "\n",
    "        j=n=len(s)\n",
    "        c=Counter()\n",
    "        while c['a']<k or c['b']<k or c['c']<k:\n",
    "            if j==0:\n",
    "                return -1\n",
    "            j-=1\n",
    "            c[s[j]]+=1\n",
    "        \n",
    "        ans=n-j\n",
    "        for i,char in enumerate(s):\n",
    "            c[s[i]]+=1\n",
    "            while j<n and c[s[j]]>k:\n",
    "                c[s[j]]-=1\n",
    "                j+=1\n",
    "            ans=min(ans,i+1+n-j)\n",
    "            if j==n:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        mp = Counter(s)\n",
    "        n = len(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        if n < 3 * k or len(mp) < 3 or any(mp[d] < k for d in mp):\n",
    "            return -1\n",
    "        res = 0\n",
    "        i,j = 0,0\n",
    "        while j < n:\n",
    "            mp[s[j]] -= 1\n",
    "            while mp[s[j]] < k:\n",
    "                mp[s[i]] += 1\n",
    "                i += 1\n",
    "            j += 1\n",
    "            res = max(res,j-i)\n",
    "        return n - res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        cnt = Counter()\n",
    "        for x in s:\n",
    "            cnt[x] += 1\n",
    "        if cnt['a'] < k or cnt['b'] < k or cnt['c'] < k:\n",
    "            return -1\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        cnt1  = Counter()\n",
    "        for r, x in enumerate(s):\n",
    "            cnt1[x] += 1\n",
    "            while cnt1[x] > cnt[x] - k:\n",
    "                cnt1[s[l]] -= 1\n",
    "                l += 1\n",
    "            ans = max(ans, r - l + 1)\n",
    "        return len(s) - ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        res=Counter()\n",
    "        n=j=len(s)\n",
    "        while res['a']<k or res['b']<k or res['c']<k:\n",
    "            if j==0:\n",
    "                return -1\n",
    "            j-=1\n",
    "            res[s[j]]+=1\n",
    "        ans=n-j\n",
    "\n",
    "        for i,ss in enumerate(s):\n",
    "            res[ss]+=1\n",
    "            while j<n and res[s[j]]>k:\n",
    "                res[s[j]]-=1\n",
    "                j+=1\n",
    "            ans=min(ans,i+1+n-j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        j = n = len(s)\n",
    "        c = Counter()\n",
    "        while c['a'] < k or c['b'] < k or c['c'] < k:\n",
    "            if j == 0: return -1  # 所有字母都取也无法满足要求\n",
    "            j -= 1\n",
    "            c[s[j]] += 1\n",
    "        ans = n - j  # 左侧没有取字符\n",
    "        for i, ch in enumerate(s):\n",
    "            c[ch] += 1\n",
    "            while j < n and c[s[j]] > k:  # 维护 j 的最大下标\n",
    "                c[s[j]] -= 1\n",
    "                j += 1\n",
    "            ans = min(ans, i + 1 + n - j)\n",
    "            if j == n: break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        j=n=len(s)\n",
    "        cnt=Counter()\n",
    "        #左端还没开始删，满足要求的最大右端下标j\n",
    "        while cnt['a']<k or cnt['b']<k or cnt['c']<k:\n",
    "            if j==0:\n",
    "                return -1\n",
    "            j-=1\n",
    "            cnt[s[j]]+=1\n",
    "        ans=n-j  #ans代表返回的分钟数，左侧没有开始删，此时ans=n-j\n",
    "        #从左边开始遍历\n",
    "        for i, ch in enumerate(s):\n",
    "            cnt[ch]+=1\n",
    "            #左边的下标固定时，右边可以拿到的最大下标\n",
    "            while j < n and cnt[s[j]] > k:\n",
    "                cnt[s[j]]-=1\n",
    "                j+=1\n",
    "            ans = min(ans, i+1+n-j)\n",
    "            #当右边已经到n-1时，跳出循环（再循环下去，ans不可能比此时更小）\n",
    "            if j==n:\n",
    "                break\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if len(s) < 3 * k:\n",
    "            return -1\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        cc = Counter()\n",
    "        j = len(s)\n",
    "        while(cc['a'] < k or cc['b'] < k or cc['c'] <k):\n",
    "            if j == 0:\n",
    "                return -1\n",
    "            j -= 1\n",
    "            cc[s[j]] += 1\n",
    "                    \n",
    "        ans = len(s) - j\n",
    "        for i, ch in enumerate(s):\n",
    "            cc[ch] += 1\n",
    "            while (j < len(s) and cc[s[j]] > k):\n",
    "                cc[s[j]] -= 1\n",
    "                j += 1\n",
    "            \n",
    "            ans = min(ans, (i + 1 + len(s) - j))\n",
    "\n",
    "            if j == len(s):\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        right = n\n",
    "        cnt = Counter()\n",
    "        while cnt[\"a\"] < k or cnt[\"b\"] < k or cnt[\"c\"] < k:\n",
    "            if right == 0:\n",
    "                return -1\n",
    "            right -= 1\n",
    "            cnt[s[right]] += 1\n",
    "        ans = n - right\n",
    "        for left in range(n):\n",
    "            cnt[s[left]] += 1\n",
    "            while right < n and cnt[s[right]] > k:\n",
    "                cnt[s[right]] -= 1\n",
    "                right += 1\n",
    "            ans = min(ans, left + n - right + 1)\n",
    "            if right == n:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        m = len(s)\n",
    "        tmp = [-k, -k, -k]\n",
    "        for value in s:\n",
    "            tmp[ord(value) - ord(\"a\")] += 1\n",
    "        if not all(i >= 0 for i in tmp):\n",
    "            return -1\n",
    "        i = 0\n",
    "        res = 0\n",
    "        l1 = [0, 0, 0]\n",
    "        for j in range(m):\n",
    "            l1[ord(s[j]) - ord(\"a\")] += 1\n",
    "            while i <= j and (l1[0] > tmp[0] or l1[1] > tmp[1] or l1[2] > tmp[2]):\n",
    "                l1[ord(s[i]) - ord(\"a\")] -= 1\n",
    "                i += 1\n",
    "            res = max(res, j - i + 1)\n",
    "\n",
    "        return m - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution2(object):\n",
    "    def takeCharacters(self, s, k):\n",
    "        c = Counter(s)\n",
    "        if any(c[a] < k for a in 'abc'):\n",
    "            return -1\n",
    "\n",
    "        res = n = len(s)\n",
    "        left = 0\n",
    "        for right, ch in enumerate(s):\n",
    "            c[ch] -= 1\n",
    "            while any(c[a] < k for a in 'abc'):\n",
    "                c[s[left]] += 1\n",
    "                left += 1\n",
    "            res = min(res, n - (right - left + 1))\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if not k:\n",
    "            return 0\n",
    "\n",
    "        record = Counter(s)\n",
    "\n",
    "        if len(record) < 3:\n",
    "            return -1\n",
    "\n",
    "        for num in record.values():\n",
    "            if num < k:\n",
    "                return -1\n",
    "\n",
    "        res = len(s)\n",
    "        left, right = 0, 0\n",
    "\n",
    "        num = set(record.keys())\n",
    "        while right < len(s):\n",
    "            record[s[right]] -= 1\n",
    "            if record[s[right]] < k:\n",
    "                num.remove(s[right])\n",
    "            right += 1\n",
    "\n",
    "            while left <= right and left < len(s) and len(num) < 3:\n",
    "                record.setdefault(s[left], 0)\n",
    "                record[s[left]] += 1\n",
    "                if record[s[left]] >= k:\n",
    "                    num.add(s[left])\n",
    "                left += 1\n",
    "\n",
    "            if len(num) == 3:\n",
    "                res = min(res, len(s) - (right - left))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0 \n",
    "        if s.count('a') < k or s.count('b') < k or s.count('c') < k:\n",
    "            return -1 \n",
    "        n = len(s)\n",
    "        l1, l2, l3 = 0, 0, 0\n",
    "        #r = n \n",
    "        c1, c2, c3 = 0, 0, 0\n",
    "        while l1 < n and c1 < k:\n",
    "            c1+=(1 if s[l1] == 'a' else 0) \n",
    "            l1+=1\n",
    "        while l2 < n and c2 < k:\n",
    "            c2+=(1 if s[l2] == 'b' else 0)\n",
    "            l2+=1\n",
    "        while l3 < n and c3 < k:\n",
    "            c3+=(1 if s[l3] == 'c' else 0)\n",
    "            l3+=1 \n",
    "        #print(l1, l2, l3, c1, c2, c3)\n",
    "        ans = max(max(l1, l2), l3) \n",
    "        for r in range(n-1, -1, -1):\n",
    "            if s[r] == 'a':\n",
    "                c1 += 1\n",
    "            elif s[r] == 'b':\n",
    "                c2 += 1\n",
    "            else:\n",
    "                c3 += 1\n",
    "            while l1 > 0 and (c1 > k or s[l1-1] != 'a'):\n",
    "                if s[l1-1] == 'a':\n",
    "                    c1 -= 1\n",
    "                l1 -= 1\n",
    "            while l2 > 0 and (c2 > k or s[l2-1] != 'b'):\n",
    "                if s[l2-1] == 'b':\n",
    "                    c2 -= 1\n",
    "                l2 -= 1\n",
    "            while l3 > 0 and (c3 > k or s[l3-1] != 'c'):\n",
    "                if s[l3-1] == 'c':\n",
    "                    c3 -= 1\n",
    "                l3 -= 1\n",
    "            #print(n-r, l1, l2, l3,c1, c2, c3)\n",
    "            tmp = max(max(l1, l2), l3) + n-r\n",
    "            ans = min(ans, tmp) \n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "      n = len(s)\n",
    "      if(n < 3 * k):\n",
    "        return -1\n",
    "      j = n\n",
    "      cnt = Counter()\n",
    "      while cnt['a'] <  k or cnt['b'] < k or cnt['c'] < k:\n",
    "        if(j == 0): \n",
    "          return -1\n",
    "        j -= 1\n",
    "        cnt[s[j]] += 1\n",
    "      \n",
    "      res = n - j\n",
    "      for i, ch in enumerate(s):\n",
    "        cnt[ch] += 1\n",
    "        while(j < n and cnt[s[j]] > k):\n",
    "          cnt[s[j]] -= 1\n",
    "          j += 1\n",
    "        res = min(res, i + 1 + n - j)\n",
    "        if j == n:\n",
    "          break\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if not k:\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        cnt = Counter()\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            cnt[s[i]] += 1\n",
    "            if cnt['a'] >= k and cnt['b'] >= k and cnt['c'] >= k:\n",
    "                ans = min(ans, i + 1)\n",
    "                break\n",
    "        \n",
    "        cnt = Counter()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt[s[i]] += 1\n",
    "            if cnt['a'] >= k and cnt['b'] >= k and cnt['c'] >= k:\n",
    "                ans = min(ans, n - i)\n",
    "                break\n",
    "        \n",
    "        ns = s + s\n",
    "        m = len(ns)\n",
    "        l = 0\n",
    "        cnt = Counter()\n",
    "        for r in range(m):\n",
    "            cnt[ns[r]] += 1\n",
    "            while l <= r and cnt[ns[l]] > k:\n",
    "                cnt[ns[l]] -= 1\n",
    "                l += 1\n",
    "            if cnt['a'] >= k and cnt['b'] >= k and cnt['c'] >= k:\n",
    "                if r >= n and l < n:\n",
    "                    ans = min(ans, r - l + 1)\n",
    "        return ans if ans <= n else -1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        mp = {'a':-k, 'b':-k, 'c':-k}\n",
    "        for c in s:\n",
    "            mp[c] += 1\n",
    "        if(mp['a'] < 0 or mp['b'] < 0 or mp['c'] < 0):\n",
    "            return -1\n",
    "        def check(mapping):\n",
    "            return mapping['a'] <= mp['a'] and mapping['b'] <= mp['b'] and mapping['c'] <= mp['c']\n",
    "        result = float('inf')\n",
    "        mapping = {'a':0, 'b':0, 'c':0}\n",
    "        left, right = 0, 0\n",
    "        while(right < n):\n",
    "            mapping[s[right]] += 1\n",
    "            while(left <= right and not check(mapping)):\n",
    "                mapping[s[left]] -= 1\n",
    "                left += 1\n",
    "            if(check(mapping)):\n",
    "                result = min(result, n - (right-left+1))\n",
    "            right += 1\n",
    "        return result\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        # 最少取外面，最多取里面\n",
    "        cnt = Counter(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        if min(cnt.values()) < k or len(cnt.keys()) < 3:\n",
    "            return -1\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for right, x in enumerate(s):\n",
    "            cnt[x] -= 1\n",
    "            while cnt[x] < k:\n",
    "                cnt[s[left]] += 1\n",
    "                left += 1\n",
    "            ans = max(ans,right-left+1)\n",
    "        return len(s) - ans\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        dic = {'a':0,'b':0,'c':0}\n",
    "        j = n = len(s)\n",
    "        while dic['a'] < k or dic['b'] < k or dic['c']< k:\n",
    "            if j == 0:\n",
    "                return -1\n",
    "            j -= 1\n",
    "            dic[s[j]] += 1\n",
    "        res = n-j\n",
    "        for i, c in enumerate(s):\n",
    "            dic[c] += 1\n",
    "            while j < n and dic[s[j]] > k:\n",
    "                dic[s[j]] -= 1\n",
    "                j += 1\n",
    "            res = min(res, i+1+n-j)\n",
    "            if j == n:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution2(object):\n",
    "    def takeCharacters(self, s, k):\n",
    "        c = Counter(s)\n",
    "        if any(c[a] < k for a in 'abc'):\n",
    "            return -1\n",
    "\n",
    "        res = n = len(s)\n",
    "        left = 0\n",
    "        for right, ch in enumerate(s):\n",
    "            c[ch] -= 1\n",
    "            while any(c[a] < k for a in 'abc'):\n",
    "                c[s[left]] += 1\n",
    "                left += 1\n",
    "            res = min(res, n - (right - left + 1))\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        # 不用取\n",
    "        if not k:\n",
    "            return 0\n",
    "\n",
    "        record = Counter(s)\n",
    "\n",
    "        if len(record) < 3:\n",
    "            return -1\n",
    "\n",
    "        if any(num < k for num in record.values()):\n",
    "            return -1\n",
    "\n",
    "        res = len(s)\n",
    "        left, right = 0, 0\n",
    "\n",
    "        num = set(record.keys())\n",
    "        while right < len(s):\n",
    "            record[s[right]] -= 1\n",
    "            if record[s[right]] < k:\n",
    "                num.remove(s[right])\n",
    "            right += 1\n",
    "\n",
    "            while left <= right and left < len(s) and len(num) < 3:\n",
    "                record.setdefault(s[left], 0)\n",
    "                record[s[left]] += 1\n",
    "                if record[s[left]] >= k:\n",
    "                    num.add(s[left])\n",
    "                left += 1\n",
    "\n",
    "            if len(num) == 3:\n",
    "                res = min(res, len(s) - (right - left))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        cnt = Counter(s)\n",
    "        if not all(cnt[x] >= k for x in 'abc'): return -1\n",
    "\n",
    "        left = ans = 0\n",
    "        for right, c in enumerate(s):\n",
    "            cnt[c] -= 1\n",
    "            while min(cnt[x] for x in 'abc') < k:\n",
    "                cnt[s[left]] += 1\n",
    "                left += 1\n",
    "            if min(cnt[x] for x in 'abc') == k:\n",
    "                ans = max(ans,right-left+1)\n",
    "\n",
    "        return len(s)-ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        j = n\n",
    "        cnt = defaultdict(int)\n",
    "        # 不取走左侧字符的情况\n",
    "        while cnt['a'] < k or cnt['b'] < k or cnt ['c'] < k:\n",
    "            if j == 0: return -1\n",
    "            j -= 1\n",
    "            cnt[s[j]] += 1\n",
    "        res = n - j\n",
    "\n",
    "        # 取走左侧字符的情况\n",
    "        for i, c in enumerate(s):\n",
    "            cnt[c] += 1\n",
    "            while j < n and cnt[s[j]] > k:\n",
    "                cnt[s[j]] -= 1\n",
    "                j += 1\n",
    "            res = min(res, i + n - j + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        cnts = collections.Counter(s)\n",
    "\n",
    "        if not(len(cnts) == 3 and min(cnts.values()) >= k):\n",
    "            return -1\n",
    "\n",
    "        left = 3\n",
    "        right = len(s)\n",
    "\n",
    "        def check(tar):\n",
    "            size = len(s) - tar\n",
    "\n",
    "            a, b, c = 0, 0, 0\n",
    "\n",
    "            for i in range(size):\n",
    "                if s[i] == 'a':\n",
    "                    a += 1\n",
    "                elif s[i] == 'b':\n",
    "                    b += 1\n",
    "                else:\n",
    "                    c += 1\n",
    "            \n",
    "            a_, b_, c_ = cnts['a'] - a, cnts['b'] - b, cnts['c'] - c\n",
    "\n",
    "            if a_ >= k and b_ >= k and c_ >= k:\n",
    "                return True\n",
    "\n",
    "            left = 0\n",
    "            right = size - 1\n",
    "\n",
    "            left += 1\n",
    "            right += 1\n",
    "\n",
    "            while right < len(s):\n",
    "                if s[right] == 'a':\n",
    "                    a += 1\n",
    "                elif s[right] == 'b':\n",
    "                    b += 1\n",
    "                else:\n",
    "                    c += 1\n",
    "                \n",
    "                if s[left - 1] == 'a':\n",
    "                    a -= 1\n",
    "                elif s[left - 1] == 'b':\n",
    "                    b -= 1\n",
    "                else:\n",
    "                    c -= 1\n",
    "                \n",
    "                a_, b_, c_ = cnts['a'] - a, cnts['b'] - b, cnts['c'] - c\n",
    "\n",
    "                if a_ >= k and b_ >= k and c_ >= k:\n",
    "                    return True\n",
    "\n",
    "                left += 1\n",
    "                right += 1\n",
    "                \n",
    "            return False\n",
    "\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        cnt = [0] * 3\n",
    "        for x in s:\n",
    "            cnt[ord(x) - ord('a')] += 1\n",
    "        if any(x < k for x in cnt):\n",
    "            return -1\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        cnt1 = [0] * 3\n",
    "        for r, x in enumerate(s):\n",
    "            cnt1[ord(x) - ord('a')] += 1\n",
    "            while any(cnt1[i] > cnt[i] - k for i in range(3)):\n",
    "                cnt1[ord(s[l]) - ord('a')] -= 1\n",
    "                l += 1\n",
    "            ans = max(ans, r - l + 1)\n",
    "        return len(s) - ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        d = {'a':0,'b':0,'c':0}\n",
    "        for i in range(len(s)):\n",
    "            d[s[i]] += 1\n",
    "        if d['a'] < k or d['b'] < k or d['c'] < k:\n",
    "            return -1\n",
    "        res = len(s)\n",
    "        j = 0\n",
    "        tmp = [0,0,0]\n",
    "        for i in range(len(s)):\n",
    "            if i > 0:\n",
    "                ind = ord(s[i-1]) - ord('a')\n",
    "                tmp[ind] -= 1\n",
    "            while j < len(s):\n",
    "                if tmp[0]<=d['a']-k and tmp[1]<=d['b']-k and tmp[2]<=d['c']-k:\n",
    "                    res = min(res,len(s)-(j-i))\n",
    "                    index = ord(s[j]) - ord('a')\n",
    "                    tmp[index] += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            if tmp[0]<=d['a']-k and tmp[1]<=d['b']-k and tmp[2]<=d['c']-k:\n",
    "                res = min(res,len(s)-(j-i))\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        acount,bcount,ccount=s.count('a'),s.count('b'),s.count('c');\n",
    "        collection={'a':0,'b':0,'c':0};\n",
    "        maxlength=0;\n",
    "        index=0;\n",
    "        if acount<k or bcount<k or ccount<k:return -1;\n",
    "\n",
    "        for i,v in enumerate(s):\n",
    "            collection[v]+=1;\n",
    "            if acount-collection['a']<k or bcount-collection['b']<k or ccount-collection['c']<k:\n",
    "                collection[s[index]]-=1;\n",
    "                index+=1;\n",
    "\n",
    "            maxlength=max(maxlength,i-index+1);\n",
    "\n",
    "        return len(s)-maxlength;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def takeCharacters(self, s: str, k: int) -> int:\n",
    "       j = n = len(s)\n",
    "       c = Counter()\n",
    "       while c['a'] < k or c['b'] < k or c['c'] < k:\n",
    "           if j == 0: return -1  # 所有字母都取也无法满足要求\n",
    "           j -= 1\n",
    "           c[s[j]] += 1\n",
    "       ans = n - j  # 左侧没有取字符\n",
    "       for i, ch in enumerate(s):\n",
    "           c[ch] += 1\n",
    "           while j < n and c[s[j]] > k:  # 维护 j 的最大下标\n",
    "               c[s[j]] -= 1\n",
    "               j += 1\n",
    "           ans = min(ans, i + 1 + n - j)\n",
    "           if j == n: break\n",
    "       return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        c=collections.Counter()\n",
    "        r=n\n",
    "        while c[\"a\"]<k or c[\"b\"] < k or c[\"c\"]<k:\n",
    "            if r==0:\n",
    "                return -1\n",
    "            r=r-1\n",
    "            c[s[r]]+=1\n",
    "        ans=n-r\n",
    "\n",
    "        for l,v in enumerate(s):\n",
    "            c[s[l]]+=1\n",
    "            while  r <n and c[s[r]]>k :\n",
    "                c[s[r]]-=1\n",
    "                r+=1\n",
    "            ans=min(ans,l+1+n-r)\n",
    "            if r==n:\n",
    "                break\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        j=n\n",
    "        cnt=Counter()\n",
    "        while cnt['a']<k or cnt['b']<k or cnt['c']<k:\n",
    "            if j==0:\n",
    "                return -1\n",
    "            j-=1\n",
    "            cnt[s[j]]+=1\n",
    "            \n",
    "        ans=n-j\n",
    "\n",
    "        for i,ch in enumerate(s):\n",
    "            cnt[ch]+=1\n",
    "            while j<n and cnt[s[j]]>k:\n",
    "                cnt[s[j]]-=1\n",
    "                j+=1\n",
    "            ans=min(ans,i+1+n-j)\n",
    "            if j==n:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        if any(c not in cnt or cnt[c] < k for c in \"abc\"):  # 存在一个字符的数量没有到 k ，返回 -1\n",
    "            return -1\n",
    "        right = n\n",
    "        d = {c: 0 for c in \"abc\"}\n",
    "        # 后缀，移动 right 直到 abd 的数量都至少为 k\n",
    "        while right and any(v < k for v in d.values()):\n",
    "            right -= 1\n",
    "            d[s[right]] += 1\n",
    "        ans = n - right\n",
    "        left = 0\n",
    "        while left <= right:  # 可以等于，当等于的时候，一定会启动里面这个 while，并更新 ans\n",
    "            ch = s[left]\n",
    "            d[ch] += 1\n",
    "            while right < n and d[s[right]] - 1 >= k:\n",
    "                d[s[right]] -= 1\n",
    "                right += 1\n",
    "            ans = min(ans, left + 1 + n - right)\n",
    "            if right == n:  # 前缀已经满足“至少”\n",
    "                break\n",
    "            left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if k==0:\n",
    "            return 0\n",
    "        cnt=Counter(s)\n",
    "        if cnt['a']<k or cnt['b']<k or cnt['c']<k:\n",
    "            return -1\n",
    "        if len(s)==3*k:\n",
    "            return 3*k\n",
    "        rest=[0]*3\n",
    "        l=-1\n",
    "        for i,ch in enumerate(s):\n",
    "            rest[ord(ch)-ord('a')]+=1\n",
    "            if all([r>=k for r in rest]):\n",
    "                l=i\n",
    "                break\n",
    "        ans=l+1\n",
    "        rc=1\n",
    "        lc=l+1\n",
    "        while lc>=0:\n",
    "            rest[ord(s[-rc])-ord('a')]+=1\n",
    "            while lc>=0 and all([r>=k for r in rest]):\n",
    "                ans=min(ans,rc+lc)\n",
    "                rest[ord(s[lc-1])-ord('a')]-=1\n",
    "                lc-=1\n",
    "            rc+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        j = n = len(s)\n",
    "        c = Counter()\n",
    "        while c['a'] < k or c['b'] < k or c['c'] < k:\n",
    "            j -= 1\n",
    "            if j == -1:\n",
    "                return -1\n",
    "            else:\n",
    "                c[s[j]] += 1\n",
    "        ans = n - j\n",
    "        for i in range(n):\n",
    "            c[s[i]] += 1\n",
    "            while j < n and c[s[j]] > k:\n",
    "                c[s[j]] -= 1\n",
    "                j += 1\n",
    "            ans = min(ans, i + 1 + n - j)\n",
    "            if j == n: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        index_map = {\n",
    "            \"a\": 0,\n",
    "            \"b\": 0,\n",
    "            \"c\": 0\n",
    "        }\n",
    "        left = 0\n",
    "        right = 0\n",
    "        for i, c in enumerate(s):\n",
    "            index_map[c] += 1\n",
    "            if index_map[\"a\"] >= k and index_map[\"b\"] >= k and index_map[\"c\"] >= k:\n",
    "                right = i\n",
    "                break\n",
    "        else:\n",
    "            return -1\n",
    "        n = len(s)\n",
    "        min_re = right + 1\n",
    "        # print(right, index_map)\n",
    "        while left > (-n+1) and right > -1:\n",
    "            right_v = s[right]\n",
    "            right -= 1\n",
    "            index_map[right_v] -= 1\n",
    "            left -= 1\n",
    "            index_map[s[left]] += 1\n",
    "            while index_map[right_v] < k:\n",
    "                left -= 1\n",
    "                index_map[s[left]] += 1\n",
    "            # print(\"left\", left, right, index_map)\n",
    "            while index_map[s[right]] > k and right > -1:\n",
    "                index_map[s[right]] -= 1\n",
    "                right -= 1\n",
    "            # print(\"right\", left, right, index_map)\n",
    "            # print(\"Before: \", min_re)\n",
    "            min_re = min(min_re, right - left + 1)\n",
    "            # print(\"After: \", min_re)\n",
    "        return min_re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        j = n = len(s)\n",
    "        c = Counter()\n",
    "        while c['a'] < k or c['b'] < k or c['c'] < k:\n",
    "            if j == 0: return -1  # 所有字母都取也无法满足要求\n",
    "            j -= 1\n",
    "            c[s[j]] += 1\n",
    "        ans = n - j  # 左侧没有取字符\n",
    "        for i, ch in enumerate(s):\n",
    "            c[ch] += 1\n",
    "            while j < n and c[s[j]] > k:  # 维护 j 的最大下标\n",
    "                c[s[j]] -= 1\n",
    "                j += 1\n",
    "            ans = min(ans, i + 1 + n - j)\n",
    "            if j == n: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        if any(c not in cnt or cnt[c] < k for c in \"abc\"):  # 存在一个字符的数量没有到 k ，返回 -1\n",
    "            return -1\n",
    "        right = n\n",
    "        d = {c: 0 for c in \"abc\"}\n",
    "        while right and any(v < k for v in d.values()):\n",
    "            right -= 1\n",
    "            d[s[right]] += 1\n",
    "        ans = n - right\n",
    "        left = 0\n",
    "        while left <= right:\n",
    "            ch = s[left]\n",
    "            d[ch] += 1\n",
    "            while right < n and d[s[right]] - 1 >= k:\n",
    "                d[s[right]] -= 1\n",
    "                right += 1\n",
    "            ans = min(ans, left + 1 + n - right)\n",
    "            if right == n:\n",
    "                break\n",
    "            left += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        ans = n + 1\n",
    "        cnt = [0] * 3\n",
    "        A, B, C = 0, 0, 0\n",
    "        for x in s:\n",
    "            if ord(x) - ord('a') == 0:\n",
    "                A += 1\n",
    "            elif  ord(x) - ord('a') == 1:\n",
    "                B += 1\n",
    "            else:\n",
    "                C += 1\n",
    "        left, right = 0, 0\n",
    "        while right < n:\n",
    "            cnt[ord(s[right]) - ord('a')] += 1\n",
    "            right += 1\n",
    "            while left < right and min(A - cnt[0], B - cnt[1], C - cnt[2]) < k:\n",
    "                cnt[ord(s[left]) - ord('a')] -= 1\n",
    "                left += 1\n",
    "            if min(A - cnt[0], B - cnt[1], C - cnt[2]) >= k:\n",
    "                ans = min(ans, n - (right - left))\n",
    "        if ans == n + 1:\n",
    "            ans = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        x=n\n",
    "        if k==0:\n",
    "            return 0 \n",
    "        if len(s)<3*k:\n",
    "            return -1\n",
    "        d={'a':0,'b':0,'c':0}\n",
    "        for i in range(n):\n",
    "            d[s[i]]+=1\n",
    "            if d['a']>=k and d['b']>=k and d['c']>=k:\n",
    "                x=i\n",
    "                ans=i+1\n",
    "                break\n",
    "        if x==n:\n",
    "            return -1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            d[s[i]]+=1\n",
    "            t=x\n",
    "            while d['a']>=k and d['b']>=k and d['c']>=k and x>=0:\n",
    "                d[s[x]]-=1\n",
    "                x-=1\n",
    "            if x==-1:\n",
    "                if d['a']>=k and d['b']>=k and d['c']>=k:\n",
    "                    return min(ans,n-i)\n",
    "            x+=1\n",
    "            d[s[x]]+=1\n",
    "            if x+n-i+1<ans:\n",
    "                ans=x+n-i+1\n",
    "            if n-i>ans:\n",
    "                break\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        # aabaaaacaabc 8a2b2c, k=2 left:6a0b0c最多6a不能有bc 最长为4\n",
    "        c_all = Counter(s)\n",
    "        for c in 'abc':\n",
    "            if c_all[c]<k:\n",
    "                return -1\n",
    "            c_all[c]-=k\n",
    "        l=0\n",
    "        n=len(s)\n",
    "        ans=inf\n",
    "        cc=Counter()\n",
    "        for r,c in enumerate(s):\n",
    "            cc[c]+=1\n",
    "            while cc[c]>c_all[c]:\n",
    "                cc[s[l]]-=1\n",
    "                l+=1\n",
    "            len1 = r-l+1\n",
    "            ans=min(ans, n-len1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        s_length = len(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        if 3 * k > s_length:\n",
    "            return -1 \n",
    "    \n",
    "        s_Counter = Counter(s)\n",
    "        if 'a' not in s_Counter or s_Counter['a'] < k:\n",
    "            return -1\n",
    "        if 'b' not in s_Counter or s_Counter['b'] < k:\n",
    "            return -1\n",
    "        if 'c' not in s_Counter or s_Counter['c'] < k:\n",
    "            return -1\n",
    "        if s_length == 3 * k:\n",
    "            return s_length \n",
    "\n",
    "        answer = s_length\n",
    "        left = 0\n",
    "        right = left\n",
    "        while left < s_length:\n",
    "            while s_Counter['a'] >= k and s_Counter['b'] >= k and s_Counter['c'] >= k:\n",
    "                answer = min(answer, s_length - (right - left))\n",
    "                if right < s_length:\n",
    "                    s_Counter[s[right]] -= 1 \n",
    "                    right += 1  \n",
    "                else:\n",
    "                    break                \n",
    "            s_Counter[s[left]] += 1 \n",
    "            left += 1 \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        j = n = len(s)\n",
    "        c = Counter()\n",
    "        while c['a'] < k or c['b'] < k or c['c'] < k:\n",
    "            if j == 0: return -1  # 所有字母都取也无法满足要求\n",
    "            j -= 1\n",
    "            c[s[j]] += 1\n",
    "        ans = n - j  # 左侧没有取字符\n",
    "        for i, ch in enumerate(s):\n",
    "            c[ch] += 1\n",
    "            while j < n and c[s[j]] > k:  # 维护 j 的最大下标\n",
    "                c[s[j]] -= 1\n",
    "                j += 1\n",
    "            ans = min(ans, i + 1 + n - j)\n",
    "            if j == n: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        m = len(s)\n",
    "        tmp = [-k, -k, -k]\n",
    "        for value in s:\n",
    "            tmp[ord(value) - ord(\"a\")] += 1\n",
    "        if not all(i >= 0 for i in tmp):\n",
    "            return -1\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for j in range(m):\n",
    "            tmp[ord(s[j]) - ord(\"a\")] -= 1\n",
    "            while i <= j and (tmp[0] < 0 or tmp[1] < 0 or tmp[2] < 0):\n",
    "                tmp[ord(s[i]) - ord(\"a\")] += 1\n",
    "                i += 1\n",
    "            res = max(res, j - i + 1)\n",
    "\n",
    "        return m - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if not k:\n",
    "            return 0\n",
    "        s += s\n",
    "        c = Counter(s[0])\n",
    "        l, r = 0, 0\n",
    "        ans = inf\n",
    "        while l < len(s) // 2:\n",
    "            if r - l + 1 > len(s) // 2:\n",
    "                return -1\n",
    "            if c['a'] >= k and c['b'] >= k and c['c'] >= k:\n",
    "                can = max(0, len(s)// 2 - 1 - r) if l else 0\n",
    "                ans = can + r - l + 1 if can + r - l + 1 < ans else ans\n",
    "                c[s[l]] -= 1\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "                c[s[r]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    正难则反\n",
    "    \"\"\"\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        cnt_s = Counter(s)\n",
    "        target = {'a': cnt_s['a'] - k, 'b': cnt_s['b'] - k, 'c': cnt_s['c'] - k}\n",
    "        #print(target)\n",
    "        if cnt_s['a'] - k < 0 or cnt_s['b'] - k < 0 or cnt_s['c'] - k < 0:\n",
    "            return -1\n",
    "        left = right = 0\n",
    "\n",
    "        cnt = Counter()\n",
    "        res = 0\n",
    "        while right < len(s):\n",
    "            cnt[s[right]] += 1\n",
    "            while cnt[s[right]] > target[s[right]]:\n",
    "                cnt[s[left]] -= 1\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return len(s) - res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "反正只有a，b，c\n",
    "分开枚举就可以了，\n",
    "对于每个字符\n",
    "维护left和right，要让left尽量小，right尽量大，可以试试双指针，又来了哈\n",
    "这个思路好像不太对,寄了寄了,服了啊\n",
    "\n",
    "猜一个k，需要花费2*k的时间判断是否正确\n",
    "'''\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        if k==0:return 0\n",
    "        cnt=Counter(s)  \n",
    "        if cnt['a']<k or cnt['b']<k or cnt['c']<k:\n",
    "            return -1\n",
    "        def check(minu:int)->bool:\n",
    "            #枚举右端点\n",
    "            cnt_a,cnt_b,cnt_c=0,0,0\n",
    "            for left in range(0,minu,1):\n",
    "                if s[left]=='a':cnt_a+=1\n",
    "                if s[left]=='b':cnt_b+=1\n",
    "                if s[left]=='c':cnt_c+=1\n",
    "            if cnt_a>=k and cnt_b>=k and cnt_c>=k:\n",
    "                return True\n",
    "            for right in range(n-1,n-minu-1,-1):\n",
    "                if s[right]=='a':cnt_a+=1\n",
    "                if s[right]=='b':cnt_b+=1\n",
    "                if s[right]=='c':cnt_c+=1\n",
    "                \n",
    "                if s[left]=='a':cnt_a-=1\n",
    "                if s[left]=='b':cnt_b-=1\n",
    "                if s[left]=='c':cnt_c-=1\n",
    "                left-=1\n",
    "                if cnt_a>=k and cnt_b>=k and cnt_c>=k:\n",
    "                    return True\n",
    "            return False\n",
    "        left=0\n",
    "        right=n\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                right=mid  \n",
    "            else:\n",
    "                left=mid\n",
    "        return right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        if not k: return 0\n",
    "        N = len(s)\n",
    "        s += s\n",
    "        ordA = ord('a')\n",
    "        ks = [[] for _ in range(3)]\n",
    "        for i, c in enumerate(s):\n",
    "            c = ord(c) - ordA\n",
    "            ks[c].append(i)\n",
    "        left = right = 0\n",
    "        offs = []\n",
    "        for _ks in ks:\n",
    "            if len(_ks) < k or _ks[k-1] >= N: return -1\n",
    "            left = max(left, _ks[k-1] + 1)\n",
    "            off = bisect_right(_ks, N-1) - k\n",
    "            right = max(right, N - _ks[off])\n",
    "            offs.append(off)\n",
    "        res = min(left, right)\n",
    "        for r in range(N, N*2):\n",
    "            offs[ord(s[r])-ordA] += 1\n",
    "            l = min(_ks[off] for off, _ks in zip(offs, ks))\n",
    "            if l >= N: break\n",
    "            res = min(res, r - l + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def takeCharacters(self, s: str, k: int) -> int:\n",
    "        def check(x):\n",
    "            w = i = n - x\n",
    "            while i < n + 1:\n",
    "                a, b, c = cnt[i][0] - cnt[i - w][0], cnt[i][1] - cnt[i - w][1], cnt[i][2] - cnt[i - w][2]\n",
    "                if min(ma - a, mb - b, mc - c) >= k:\n",
    "                    return True\n",
    "                i += 1\n",
    "            return False\n",
    "\n",
    "        n = len(s)\n",
    "        cnt = [[0] * 3 for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            cnt[i + 1] = cnt[i][::]\n",
    "            cnt[i + 1][ord(s[i]) - ord('a')] += 1\n",
    "        ma, mb, mc = cnt[n]\n",
    "        if min(ma, mb, mc) < k:\n",
    "            return -1\n",
    "        l, r = 0, n\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if not check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
